package sort.leetcode.hard;

/**
 * @author bruin_du
 * @description 合并排序链表
 * @date 2022/9/2 23:51
 **/
public class OfferII078_MergeKLists {
    public ListNode mergeKLists(ListNode[] lists) {
        // 方法一：迭代写法
        method1(lists);

        // 方法二：递归写法
        if (lists == null || lists.length == 0) return null;
        return method2(lists, 0, lists.length - 1);
    }

    private ListNode method1(ListNode[] lists) {
        if (lists == null || lists.length == 0) return null;
        int before = lists.length, n = lists.length;
        while (before > 1) {
            int index = 0;
            for (int i = 0; i < before; i += 2) {
                if (i + 1 < before) {
                    ListNode list = merge(lists[i], lists[i + 1]);
                    lists[index++] = list;
                } else {
                    lists[index++] = lists[i];
                }
            }
            before = index;
        }
        return lists[0];
    }

    private ListNode method2(ListNode[] lists, int left, int right) {
        if (left >= right) return lists[left];
        int mid = left + (right - left >> 1);
        return merge(method2(lists, left, mid), method2(lists, mid + 1, right));
    }

    private ListNode merge(ListNode list1, ListNode list2) {
        ListNode dummyHead = new ListNode(0);
        ListNode cur = dummyHead;
        while (list1 != null && list2 != null) {
            if (list1.val < list2.val) {
                cur = cur.next = list1;
                list1 = list1.next;
            } else {
                cur = cur.next = list2;
                list2 = list2.next;
            }
        }
        if (list2 != null) {
            list1 = list2;
        }
        cur.next = list1;
        return dummyHead.next;
    }

}
